/*
* Tree header file
* created by psych0der on 12:46 am 11th feb 2012
* (c) psych0der all rights reserved

*/

#include <iostream>
#include <string>
#include <iomanip>
#include "TreeNode.h"

using namespace std;

template <typename TNODETYPE>
class Tree
{

private:

TNode<TNODETYPE>  * root;
void insertNodeHelper(TNode<TNODETYPE>  **, TNODETYPE &);
void preOrderHelper(TNode<TNODETYPE> *); // can be declared as const
void inOrderHelper(TNode<TNODETYPE> *); // can be declared as const
void postOrderHelper(TNode<TNODETYPE> *); // can be declared as const


public:
Tree();
void insertNode(TNODETYPE &);
void preOrderTraversal();
void inOrderTraversal();
void postOrderTraversal();
int delNode(TNODETYPE &); // only asks for information to be deleted

};

template <typename TNODETYPE>
Tree<TNODETYPE>::Tree()
{

root = 0; // to indicate null initial condition

}


template <typename TNODETYPE>
void Tree<TNODETYPE>::insertNode(TNODETYPE &val)
{
insertNodeHelper(&root,val);
}

template <typename TNODETYPE>
void Tree<TNODETYPE>::insertNodeHelper(TNode<TNODETYPE> **ptr, TNODETYPE & val)
{


if(*ptr==NULL)
{
*ptr = new TNode<TNODETYPE>(val);
(*ptr)->data = val;
//cout<<"data entered --"<<(*ptr)->data;

}

else
{

if((*ptr)->data > val)
{
insertNodeHelper(&((*ptr)->lptr),val); // sending the address of the ptr
}

else if((*ptr)->data < val)
{
insertNodeHelper(&((*ptr)->rptr),val); // sending the address of the pointer

}
 else
{

cout<<"\n data item"<<val<<" already exists \n";

}

}



}


template<typename TNODETYPE>
void Tree<TNODETYPE>::preOrderTraversal()
{

preOrderHelper(root);

}

template<typename TNODETYPE>

void Tree<TNODETYPE>::preOrderHelper(TNode<TNODETYPE> *ptr)
{

if(ptr!=NULL)
{
cout<<"-"<<ptr->data;
preOrderHelper(ptr->lptr);
preOderHelper(ptr->rptr);
}


}

template<typename TNODETYPE>
void Tree<TNODETYPE>::inOrderTraversal()
{

inOrderHelper(root);

}

template<typename TNODETYPE>

void Tree<TNODETYPE>::inOrderHelper(TNode<TNODETYPE> *ptr)
{

if(ptr!=NULL)
{
inOrderHelper(ptr->lptr);
cout<<"-"<<ptr->data;
inOrderHelper(ptr->rptr);
}


}

template<typename TNODETYPE>
void Tree<TNODETYPE>::postOrderTraversal()
{

postOrderHelper(root);

}

template<typename TNODETYPE>

void Tree<TNODETYPE>::postOrderHelper(TNode<TNODETYPE> *ptr)
{

if(ptr!=NULL)
{
postOrderHelper(ptr->lptr);
postOderHelper(ptr->rptr);
cout<<"-"<<ptr->data;
}


}

template<typename TNODETYPE>
int Tree<TNODETYPE>::delNode(TNODETYPE &info)
{
	
	
	TNode<TNODETYPE> * x,*parent,*p,*subparent,*delleft,*root1;
	root1 = root;
	x=root;
	int fnd,dir;
	dir=0;
	fnd=0;
	parent=root1;
	while(x!=NULL)
	{
	if(info==x->data)
	{
	fnd=1;
	break;
	}
	else if(info>x->data)
	{
	parent=x;
	x=x->rptr;
	dir=2;
	fnd=0;
	}
	else if(info<x->data)
	{
	parent=x;
	x=x->lptr;
	fnd=0;
	dir=1;
	}
	}

	if(fnd==1)
	{
	delleft=x->lptr;

	if(x->lptr==NULL && x->rptr==NULL)
	{
	  if(dir==1)
	  {
	  parent->lptr=NULL;
	  return 1;
	  }
	  else if(dir==2)
	  {
	  parent->rptr=NULL;
	  return 1;
	  }
	  }
	 else if(x->lptr==NULL || x->rptr==NULL)
	 {
	 TNode<TNODETYPE> *chld;
	 if(x->lptr!=NULL)
	 {
	 chld=x->lptr;
	 }
	 else
	 chld=x->rptr;
	 if(dir==1)
	 {
	 parent->lptr=chld;
	 return 1;
	 }
	 else if  (dir==2)
	 {
	 parent->rptr=chld;
	 return 1;
	 }
	}
	else if (x->lptr!=NULL && x->rptr!=NULL)
	{
	 TNode<TNODETYPE> *subchld,*subparent,*g,*z;
	g=x->rptr;
	if(g->lptr==NULL)
	{
	if(dir==1)
	{
	parent->lptr=g;
	g->lptr=delleft;
	return 1;
	}
	else if(dir==2)
	{
	parent->rptr=g;
	g->lptr=delleft;
	return 1;
	}
	}
	else
	{
	subparent=g;
	while(g->lptr!=NULL)
	{
	 subparent=g;
	 g=g->lptr;
	 }
	z=g->rptr;
	subparent->lptr=z;
	x->data=g->data;
	return 1;

	}
	}
	}
	else
	{
	cout<<"\n item not found \n";
	}

	return -1;	
	
	
}


































